如果說，動態規劃是個穩穩地將所有可能的狀態逐一計算、集中並且化簡。那麼貪婪法(Greedy Algorithm) 就是另一個方向：通常僅考慮一小部分的狀態計算，因為我們能夠證明依照當前的最佳的選擇就是對整體來說最好的選擇。

有的時候，利用這個想法，我們可以利用數學證明減少需要計算的狀態數！最單純的例子就是 LCS 在解很大的時候的 O((n-LCS)n+1) 時間解法：我們只要考慮對角線附近的格子就行了。

Exercise 44: Leetcode 321 - Create Maximum Number

題目連結

https://leetcode.com/problems/create-maximum-number/

題目敘述

給你兩個陣列的數字，請從中挑出 k 個數字拼起來得到最大的十進位數字。拼起來的時候挑出來的數字必須要保持在兩陣列中的順序。

解題思考

通常在解字典順序的時候，我會喜歡從陣列的末端做回來。我們令 dp(i, j, r) 表示用 A[i...] 和 B[j...] 湊出長度為 r 的序列時，最大的一個序列是多少。

dp(i, j, r) ← dp(i+1, j, r) or dp(i, j+1, r) or A[i]+dp(i+1, j, r-1) or B[j] + dp(i, j+1, r-1)

但可惜這樣是 O(N^2K^2) 的，可能會超過時間。

換一個方法想，如果我們枚舉第一個陣列強迫選 r 個，另外一個陣列強迫選 k-r 個。各自湊出字典順序最大的陣列，再用貪婪的方法合併起來就可以得到一個 O(K^2(N+K)) 時間的演算法了！

參考程式碼 (Python3)

class Solution:

    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:

        def merge(a, b):
            c = []
            while len(a) > 0 or len(b) > 0:
                if a > b:
                    c.append(a.pop(0))
                else:
                    c.append(b.pop(0))
            return c

        def getMaxNumberByLength(a):
            l = [[]]
            for x in a:
                l.append(l[-1] + [x])
                for j in range(len(l)-3, -1, -1):
                    if l[j] + [x] > l[j+1]:
                        l[j+1] = l[j] + [x]
            return l

        l1 = getMaxNumberByLength(nums1)
        l2 = getMaxNumberByLength(nums2)
        ans = []
        for i in range(0, k+1):
            if len(l1) <= i or len(l2) <= k-i:
                continue
            p = merge(l1[i], l2[k-i])
            if p > ans:
                ans = p
        return ans

merge 函式很酷，可以合併成一行文：

def merge(a, b):
        return [max(a, b).pop(0) for _ in range(len(a) + len(b))]